/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * 
 *  输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4
 */

const LinkedList = require('../../单链表/singlylinkedlist')
var mergeTwoLists = function (l1, l2) {
    let newList = new LinkedList()
    let s = newList.head
    let p = l1.head.next
    let q = l2.head.next
    while (p !== null && q !== null) {
        if (p.data <= q.data) {
            s.next = p
            s = s.next
            p = p.next
        } else {
            s.next = q
            s = s.next
            q = q.next
        }
    }
    while(p) {
        s.next = p
        s = s.next
        p = p.next
    }
    while(q) {
        s.next = q
        s = s.next
        q = q.next
    }
    return newList
}


let l1 = LinkedList.createByArray([1, 2, 4])
let l2 = LinkedList.createByArray([1, 3, 4])

console.log(mergeTwoLists(l1, l2).toString());